#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <string>
using namespace std;

class Solution{
public:
	string addBinary(string a, string b) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		size_t s = max(a.size(),b.size());

		string result(s+1,'0');
		size_t as = a.size(), bs = b.size(), cs = s+1;
		int carry = 0;
		while((as >= 1) || (bs >= 1) || (cs>=1)){
			int t = 0;
			if( as >= 1)
				t += a[as-1]-'0';
			if(bs >= 1)
				t += b[bs-1]-'0';

			t += carry;
			result[cs-1] = t % 2 + '0';
			carry = t / 2;
			if(cs)
				cs--;
			if(as)
				as--;
			if(bs)
				bs--;
		}

		if(result[0] == '0')
			return result.substr(1,s);
		else
			return result;		
	}
};
#endif